package hot100;

public class CountSubstrings {
    public int countSubstrings(String s) {
        char[] charArray = s.toCharArray();
        int n = charArray.length;
        boolean[][] dp = new boolean[n][n];

        int count = 0;

        //倒序，这样才能保证i，j之间如果有序肯定被置为true
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (charArray[i] == charArray[j]) {
                    if (j - i <= 1) {
                        dp[i][j] = true;
                        count++;
                    } else if (dp[i + 1][j - 1]) {
                        dp[i][j] = true;
                        count++;
                    }
                }
            }
        }
        return count;
    }
}
